package 树;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 求路径和.java
 * @Description TODO
 * @createTime 2020年10月12日 20:56:00
 * 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * 3
 * 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
 *
 * 递归说到底只是一种方法 一种遍历的工具 关键在于 用它有什么好处 怎么用
 */
public class 求路径和 {
//    public class Solution {
//
//        private int ret = 0;
//
//        public int pathSum(TreeNode root, int sum) {
//            preOrder(root, sum);
//            return ret;
//        }
//        private void dfs(TreeNode root, int sum) {
//            if (root == null) {
//                return;
//            }
//            if (root.val == sum) {
//                ret++;
//            }
//            dfs(root.left, sum - root.val);
//            dfs(root.right, sum - root.val);
//        }
//
//
//        private void preOrder(TreeNode root, int sum) {
//            if (root == null) {
//                return;
//            }
//            dfs(root, sum);
//            preOrder(root.left, sum);
//            preOrder(root.right, sum);
//        }
//    }

}
